The present invention is related to data networking and more particularly to systems and methods for rerouting around failed links and/or nodes.
The Internet and IP networks in general have become enablers for a broad range of business, government, and personal activities. The Internet is being relied upon as a general information appliance, business communication tool, entertainment source, and as a substitute for traditional telephone networks and broadcast media. As the Internet expands its role, users become more and more dependent on uninterrupted access.
To assure rapid recovery in the event of failure of a network link or node, so-called “Fast Reroute” techniques have been developed. In a network employing Fast Reroute, traffic flowing through a failed link or node is rerouted through one or more preconfigured backup tunnels. The preconfigured backup tunnels facilitate a key goal of Fast Reroute techniques, the redirection of interrupted traffic within tens of milliseconds. This minimizes impact on the user experience.
The Fast Reroute techniques have been developed in the context of MPLS (Multiprotocol Label Switching) Traffic Engineering where traffic flows through label switched paths (LSPs) configured to have guaranteed bandwidth under certain conditions. When an element such as a link or node fails, all of the Traffic Engineering LSPs (also referred to as “tunnels”) using that failed element are redirected through preconfigured backup tunnels that route around the impacted segments of the LSPs. These backup tunnels are generally used only for a very short time since simultaneously with the rerouting through the backup tunnels, the head ends of all the affected primary tunnels are notified of the failure. This causes the head ends to reroute the primary tunnels around the failures so that the backup tunnels are no longer needed.
A key aspect of meeting the reliability and quality of service objectives of Fast Reroute is the switchover time from the failed segments of the protected primary tunnels to their preconfigured backup tunnels. Once a failure occurs, all of the protected traffic should be rerouted within 50 milliseconds to avoid or minimize impact on the user experience. This is a formidable task considering that the failed link may carry, e.g., 10 Gbps, 40 Gbps. There may be thousands of protected tunnels to be rerouted into a backup tunnel. The protected traffic to be rerouted may also correspond to numerous forwarding equivalence classes. Typically forwarding state within a router is represented as entries corresponding to individual forwarding equivalence classes and/or LSPs. Updating this forwarding state so that a backup tunnel will be used requires updating many of these entries. Thus the time taken to update forwarding state will vary with either the number of affected forwarding equivalence classes, the number of affected LSPs, or both. When there are large numbers of affected forwarding equivalence classes and/or LSPs, it is very difficult to meet the 50 millisecond objective.
What is needed are readily scaleable systems and methods for accelerating the switchover to preconfigured backup tunnels upon failure of a protected link or node while retaining desired features of router forwarding data structures.